#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
    void backtracking(string &digits, vector<string> &map, vector<string> &ans, string &path,  int idx) {
        if (idx == digits.size()) {
            if (path.size() != 0)
                ans.push_back(path);
            return;
        }

        int num = digits[idx] - '2';
        for (int i = 0; i < map[num].size(); i++) {
            path.push_back(map[num][i]);
            backtracking(digits, map, ans, path, idx+1);
            path.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<string> map = {
                    "abc",  "def", 
            "ghi",  "jkl",  "mno", 
            "pqrs", "tuv",  "wxyz"
        };
        vector<string> ans;
        string path;
        backtracking(digits, map, ans, path, 0);
        return ans;
    }
};

int main(void)
{

    cout << "#17. 电话号码的字母组合" << endl;
    vector<string> ans = Solution().letterCombinations("");

    for (auto e: ans) {
            cout << e << ", ";
        cout << endl;
    }
    return 0;
}